#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

// 使用pair类型别名简化代码
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second

using namespace std;

const int N = 2e5 + 10; // 定义最大节点数

// 全局变量定义
vector<int> G[N];      // 邻接表存储图
map<int, bool> vis[N]; // 记录每个节点被哪些安全点访问过
int n, m, ans[N];      // n:节点数, m:边数, ans:距离和
char s[N];             // 节点类型字符串

// BFS节点结构体
struct node {
  int x; // 当前节点
  int f; // 来源安全点
  int d; // 已走距离
};

queue<node> q; // BFS队列

// 添加边的辅助函数
void add(int x, int y) { G[x].push_back(y); }

int main() {
  // 输入节点数和边数
  scanf("%d %d", &n, &m);

  // 构建无向图
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d %d", &u, &v);
    add(u, v); // 添加边 u->v
    add(v, u); // 添加边 v->u (无向图)
  }

  // 输入节点类型字符串（索引从1开始）
  scanf("%s", s + 1);

  // 初始化：将所有安全点(S)加入BFS队列
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'S') {
      q.push(node{i, i, 0}); // 起点距离为0，来源是自己
    }
  }

  // 多源BFS主循环
  while (q.size()) {
    node t = q.front(); // 取出队列头部
    q.pop();

    // 检查访问条件：每个节点最多被两个不同的安全点访问
    // 逻辑：只有当节点被访问的安全点数量少于2个，且当前安全点没有访问过该节点时，才继续处理
    if (vis[t.x].size() > 1 || vis[t.x].count(t.f)) {
      continue; // 如果已满或已访问过，跳过
    }

    // 标记当前节点被当前安全点访问过
    vis[t.x][t.f] = 1;

    // 如果是危险点，累加距离
    if (s[t.x] == 'D') {
      ans[t.x] += t.d;
    }

    // 遍历当前节点的所有邻居
    for (auto y : G[t.x]) {
      // 检查邻居节点的访问条件
      if (vis[y].size() >= 2 || vis[y].count(t.f)) {
        continue; // 如果已满或已访问过，跳过
      }
      // 将邻居节点加入队列继续BFS
      q.push(node{y, t.f, t.d + 1});
    }
  }

  // 输出结果：对于每个危险点(D)，输出到两个最近安全点的距离和
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'D') {
      printf("%d\n", ans[i]);
    }
  }

  return 0;
}